/*
You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.

eg :

Matrix
{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}

And pattern is microsoft.

It's funny when google looks for pattern of microsoft ;)
*/


/*{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int dx[] = {1, 1, -1, -1, 0, 0, 1, -1};
int dy[] = {1, -1, 1, -1, 1, -1, 0, 0};

bool findHelper(char matrix[][5], int curX, int curY, int row, int col, vector<vector<int> > &visited, const char *str)
{
    if (*str == '\0') return true;
    
    if (curX < 0 || curY < 0 || curX >= row || curY >= col) return false;
    if (visited[curX][curY]) return false;
    if (matrix[curX][curY] != *str) return false;
    
    visited[curX][curY] = 1; 
    for (int k = 0; k < 8; k++) {
	    if (findHelper(matrix, curX + dx[k], curY + dy[k], row, col, visited, str+1)) return true;
    }
    visited[curX][curY] = 0;

    return false;
}


bool find(char matrix[][5], int row, int col, vector<vector<int> > &visited, const char *str)
{
    for (int i = 0; i < row; i++) {
	for (int j = 0; j < col; j++) {
            if (findHelper(matrix, i, j, row, col, visited, str)) return true;
	}
    }
    return false;
}

int main(int argc, char **argv)
{
    char matrix[][5] = 
    {{'A','C','P','R','C'},
     {'X','S','O','P','C'},
      {'V','O','V','N','I'},
       {'W','G','F','M','N'},
        {'Q','A','T','I','T'}};
    vector<vector<int> > visited(5, vector<int>(5, 0));
    const char *str = "MCROSOFT";
    cout << find(matrix, 5, 5, visited, str) << endl;
}
